package com.peng.leetcode.graph;

import java.util.*;

/**
 * NetworkDelayTime
 *
 * @author: lupeng6
 * @create: 2020/12/11 20:50
 */
public class NetworkDelayTime {

    public static void main(String[] args) {

    }

    static class Solution {
        public int networkDelayTime(int[][] times, int N, int K) {
            Map<Integer, List<int[]>> graph = new HashMap<>();

            // 初始化图, 从源到目的节点 和 耗时
            for (int[] node : times) {
                int source = node[0];
                int target = node[1];
                int consume = node[2];
                if (!graph.containsKey(source)) {
                    graph.put(source, new ArrayList<>());
                }
                graph.get(source).add(new int[]{target, consume});
            }

            // 从小到大的堆
            PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
            heap.offer(new int[]{K, 0});

            // 访问过的元素 和 耗时
            Map<Integer, Integer> dist = new HashMap<>();

            while (!heap.isEmpty()) {
                int[] info = heap.poll();
                int node = info[0];
                int consume = info[1];

                if (dist.containsKey(node)) {
                    continue;
                }

                dist.put(node, consume);
                if (graph.containsKey(node)) {
                    List<int[]> ints = graph.get(node);
                    for (int[] anInt : ints) {
                        int nextTarget = anInt[0];
                        int nextConsume = anInt[1];
                        if (dist.containsKey(nextTarget)) {
                            continue;
                        }

                        heap.offer(new int[]{nextTarget, consume + nextConsume});
                    }
                }
            }
            if (dist.size() != N) {
                return -1;
            }
            int ans = 0;
            for (Integer value : dist.values()) {
                ans = Math.max(value, ans);
            }
            return ans;
        }
    }
}
